import random

nums = [-74,48,-20,2,10,-84,-5,-9,11,-24,-91,2,-71,64,63,80,28,-30,-58,-11,-44,-87,-22,54,-74,-10,-55,-28,-46,29,10,50,-72,34,26,25,8,51,13,30,35,-8,50,65,-6,16,-2,21,-78,35,-13,14,23,-3,26,-90,86,25,-56,91,-13,92,-25,37,57,-20,-69,98,95,45,47,29,86,-28,73,-44,-46,65,-84,-96,-24,-12,72,-68,93,57,92,52,-45,-2,85,-63,56,55,12,-85,77,-39]

def randomized_partition(nums, l, r):
        pivot = random.randint(l, r)
        print(pivot)
        nums[pivot], nums[r] = nums[r], nums[pivot]
        i = l - 1
        for j in range(l, r):
            if nums[j] < nums[r]:
                i += 1
                nums[j], nums[i] = nums[i], nums[j]
        i += 1
        nums[i], nums[r] = nums[r], nums[i]
        return i

# 这样写更符合我的思路风格（长时间不写，第一时间想到的是 i = j = l）~
def randomized_partition(nums, l, r):
        pivot = random.randint(l, r)
        nums[pivot], nums[r] = nums[r], nums[pivot]
        i = l 
        for j in range(l, r):
            if nums[j] < nums[r]:
                nums[j], nums[i] = nums[i], nums[j]
                i += 1

        # 二向切分： 小于i 的是 小于 nums[r]的。 i 到 j 是大于等于 r，   j 之后是还没遍历到的
        nums[i], nums[r] = nums[r], nums[i]
        return i

def randomized_quicksort(nums, l, r):
    if l >= r:
        return
    mid = randomized_partition(nums, l, r)
    randomized_quicksort(nums, l, mid - 1)
    randomized_quicksort(nums, mid + 1, r)


randomized_quicksort(nums, 0, len(nums) - 1)
print(nums)

